Адміністрація вирішила продати даний сайт. За детальною інформацією звертайтесь за адресою: rozrahu@gmail.com

Асимптотичні характеристики складності алгоритму. Алгоритми з поліноміальною та експоненціальною складністю

Інформація про навчальний заклад

ВУЗ:
Національний університет Львівська політехніка
Інститут:
ІКТА
Факультет:
КН
Кафедра:
Кафедра ЕПМС

Інформація про роботу

Рік:
2014
Тип роботи:
Лабораторна робота
Предмет:
Алгоритми та методи обчислень
Варіант:
7

Частина тексту файла

Міністерство освіти і науки України Національний університет “Львівська політехніка” Кафедра ЕОМ / Звіт з лабораторної роботи № 2 з дисципліни: «Алгоритми та методи обчислень» на тему: “Асимптотичні характеристики складності алгоритму. Алгоритми з поліноміальною та експоненціальною складністю” Мета роботи: ознайомитись з асимптотичними характеристиками складності та класами складності алгоритмів. Теоретична частина В процесі розв’язку задачі вибір алгоритму викликає певні труднощі. Алгоритм повинен задовільняти вимогам, які часом суперечать одна одній: = бути простим для розуміння, переводу в програмний код, відлягодження. = ефективно використовцвати комп'ютерні ресурси і виконуватись швидко. Якщо програма повинна виконуватись декілька разів, то перша вимога більш важлива. Вартість робочого часу програміста перевищує вартість машинного часу виконання програми, тому вартість програми оптимізується по вартості написання ( а не виконання) програми. Якщо задача вимагає значних обчислювальних витрат, то вартість виконання програми може перевищити вартість написання програми, особливо коли програма повинна виконуватись багаторазово. Але навіть в цій ситуації доцільно спочатку реалізувати простий алгоритм, і з'ясувати яким чином повинна себе поводити більш складна програма. На час виконання програми впливають наступні чинники: = ввід інформації в програму = якість скомпільованого коду = машинні інструкції, які використовуються для виконання програми = часова складність алгоритму (ЧС) Часова складність є функцією від вхідних даних. Для деяких задач ЧС залежить від самих вхідних даних (знаходження найбільшого спільного дільника двох чисел), для інших – від їх "розміру" (задачі сортування). Коли ЧС є функцією від самих даних, її визначають як ЧС для найгіршого випадку, тобто як найбільшу кількість інструкцій програми серед всіх можливих вхідних даних для цього алгоритму. Використовується також ЧС в середньому ( в статистичному сенсі ), як середня кількість інструкцій по всім можливим вхідним даним. На практиці ЧС в середньому важче визначити ніж ЧС для найгіршого випадку, черезте що це математично важка для розв'язання задача, та, крім того, іноді важко визначити, що означає "середні" вхідні дані. Коли ЧС є функцією від кількості вхідних даних, аналізується швидкість зростання цієї функції. Асимптотичні співвідношення Для опису швидкості зростання функцій використовується О-символіка. Функція f(n) має порядок зростання O(g(n)), якщо що існують додатні константи С i n0 такі, що f(n) <= С*g(n), для n > n0. Позначемо функцію яка виражає залежність часової складності від кількості вхідних даних (n) через L(n) Тоді, наприклад, коли говорять, що часова складність L(n) алгоритму має порядок(степінь) зростання O(n2) (читається як "О велике від n в квадраті, або просто "о від n в квадраті", то вважається, що існують додатні константи c i n0 такі, що для всіх n, більших або рівних n0, виконується нерівність L(n)<=cn2. Наприклад, функція L(n) = 3n3+2n2 має порядок зростання O(n3). Нехай n0=0 і с = 5. Очевидно, що для всіх цілих n>=0 виконується нерівність 3n3+2n2 <= 5n3. Коли кажуть, що L(n) має степінь зростання O(f(n)) , то вважається, що f(n) є верхньою границею швидкості зростання L(n). Щоби вказати нижню границю швидкості зростання L(n) використовують позначення ((g(n)) , що означає існування такої константи с , що для нескінченогї кількості значень n виконується нерівність L(n)>=c g(n). На практиці визначення порядку зростання є задачею, що цілком вирішується за допомогою кількох базових принципів. Існують три правила для визначення складності: O(с* f(n))=O(f(n)) O(f(n) + g(n)) = O(max(f(n), g(n))) O(f(n) * g(n)) = O(f(n)) * O(g(n)) Перше правило декларує, що постійні множники не мають значення для визначення порядку зростання. Друге правило називається "Правило сум". Це правило використовується для послідовних програмних фрагментів з циклами та розгалуженнями. Порядок зроста...
Антиботан аватар за замовчуванням

27.05.2014 22:05

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, увійдіть або зареєструйтесь.

Завантаження файлу

Якщо Ви маєте на своєму комп'ютері файли, пов'язані з навчанням( розрахункові, лабораторні, практичні, контрольні роботи та інше...), і Вам не шкода ними поділитись - то скористайтесь формою для завантаження файлу, попередньо заархівувавши все в архів .rar або .zip розміром до 100мб, і до нього невдовзі отримають доступ студенти всієї України! Ви отримаєте грошову винагороду в кінці місяця, якщо станете одним з трьох переможців!
Стань активним учасником руху antibotan!
Поділись актуальною інформацією,
і отримай привілеї у користуванні архівом! Детальніше

Оголошення від адміністратора

Антиботан аватар за замовчуванням

пропонує роботу

Admin

26.02.2019 12:38

Привіт усім учасникам нашого порталу! Хороші новини - з‘явилась можливість кожному заробити на своїх знаннях та вміннях. Тепер Ви можете продавати свої роботи на сайті заробляючи кошти, рейтинг і довіру користувачів. Потрібно завантажити роботу, вказати ціну і додати один інформативний скріншот з деякими частинами виконаних завдань. Навіть одна якісна і всім необхідна робота може продатися сотні разів. «Головою заробляти» продуктивніше ніж руками! :-)

Новини